1. Field of the Invention
This invention relates to guidance and control methods for automatically guided vehicle (AGV) systems such as mobile robots and more specifically to methods for coordinating the interaction of multiple autonomous or semi-autonomous vehicles in a factory.
2. Description of the Related Art
Conventional automatically guided vehicles (AGVs) such as those used to move materials in warehouses and factories provide minimal (unidirectional) point-to-point movement control. Most such systems involve AGVs which follow a fixed guide track, usually either a radio transmitter antenna wire buried in the factory floor, a reflective stripe painted on the floor, or a reflective tape glued to the floor. Such methods are described in U.S. Pat. Nos. 4,530,056, 4,554,724, 4,562,635, 4,593,238, and 4,593,239. All of these schemes purposely limit the individual vehicle's freedom of movement by constraining the AGVs to follow a physically fixed path. Such schemes also are expensive to change due to the need to dig up or otherwise remove the existing path and reinstall it in a new configuration.
Most systems rely on on-vehicle proximity detection, such as active bumpers or ultrasonic sensors, to deal with collisions with other AGVs, stationary objects, or personnel. In such systems, the only way to prevent "deadlocks" (where two AGVs move toward each other, each senses the other, both stop, and are effectively prevented from moving again by their "locked" on-board sensors) is to forbid bidirectional travel along the path. In such cases, AGVs can move in only one direction on a given path.
FIG. 1 shows such a system. An AGV can move in only one direction in the path. To go from point A to point D, it must first pass through B and C. It cannot go directly to D. Even if the AGV itself is capable of accurate backing, a deadlock could occur if it were approached from behind by another AGV. Each AGV would sense the other and both would stop.
In those few instances where an AGV is capable of reversing, it does so by "backing up." Conventional AGV systems prohibit such motion except for individual AGVs which are under manual control (i.e., removed from the system by an operator). The guide wires or stripes contain locator strips or cross-wise antennas to provide AGV location information. Sometimes, such systems provide absolute location information by attaching bar-code markers at a fixed height along the path. When an AGV passes such a marker, it "reads" the location from the marker. Wire-guided AGVs detect the location markers via radio reception. Stripe-guided AGVs use optical detectors to sense coded reflective markers. Other AGVs, such as automated forklifts, employ bar-code scanners to decode the location markers. Altering the pathways for these systems involves considerable facilities engineering, especially in the case of those which use buried wires.
In such systems, therefore, the individual AGVs are not capable of true point-to-point motion. For example, to drive an
AGV to a particular point, the system controller commands it to move until it finds the marker for that point. The AGV effectively is "lost" to the control system until it reaches a location marker. Moreover, the AGV must follow the physical track, passing each and every intermediate marker in the physically fixed sequence, until it "reads" its destination. There is no external position sensing and reporting system to provide "closed-loop, servo-like" operation.
Since most AGVs are front-drive units, or three-wheeled vehicles similar to tricycles (one steered drive wheel in front, two differentiated trailing wheels at the rear), they have less control when moving in reverse.
In conventional multiple-AGV systems, these constraints lead to a "train" or queueing effect: when one AGV stops, all following AGVs must stop (as they approach one another). FIG. 2 shows a typical 3-vehicle loop-type AGV system. There is no way for AGV 3 to overtake AGV 2 because AGV 3's proximity detectors will prevent a collision with AGV 2 and neither AGV can leave the path to let the other pass. Furthermore, if AGV 1 stops, then AGV 2 will stop and AGV 3 will stop (as soon as their sensors detect the AGV ahead). No AGV can move until the one ahead of it moves. In other words, the individual AGVs act almost as if they were "cars" in a "train," as if they were physically connected. There is no way to send AGV 3 to a destination which lies ahead of AGV 1 unless and until both AGV 1 and AGV 2 pass that destination.
Important disadvantages in the prior art, then, are: it is limited by closed pathways, by unidirectional motion, by lack of external control of AGV motion, and by lack of independent, real-time collision avoidance. Even if these limitations somehow could be overcome, there still would remain the obstacles of "deadlock" and what to do when one AGV crosses the path of another or arrives simultaneously at the same destination as another.